package com.cty.C_SortAlgorithms.B_SelectSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/17 9:51
 * @Description: 选择排序  基于数组实现
 * @version: 1.0
 */
public class SelectSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public SelectSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int nItems(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组尾部插入  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    /**
     * 选择排序
     *      平均时间复杂度：  O(N^2)    受数据分布影响不大     s = 比较次数 + 交换次数 = N*(N-1)/2 + N-1
     *      最好情况：        O(N^2)
     *      最坏情况：        O(N^2)
     *      空间复杂度：      O(1)      不需要额外空间辅助
     *      排序方式：                  内部排序
     *      稳定性：                    不稳定                因为存在跳跃性交换，如 8 3 8 1，第一次交换的数据是1和头部的8，两个8原来的顺序被打乱
     */
    public void selectSort(){
        int in, out, min;
        for(out=0; out<nItems; out++){
            min = out;
            for(in=out+1; in<nItems; in++)  // 遍历查找最小值
                if(array[in].getKey() < array[min].getKey())
                    min = in;
            // 交换
            DataItem temp = array[min].getItem();
            array[min].setItem(array[out]);
            array[out].setItem(temp);
        }  // end for
    }  // end selectSort()










    // 练习 选择排序


}  // end SelectSort{}
